<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    /* 
    桶排序（也被称为箱排序）也是分布式排序算法，它将元素分为不同的桶（较小的数组），
    再使用一个简单的排序算法，例如插入排序（用来排序小数组的不错的算法），来对每个桶进行 排序。
    然后，它将所有的桶合并为结果数组。
    */

    /*
    bucketSize 每个小桶里的元素个数  初始化为3
    */
    function bucketSort (arr, bucketSize = 3) {
      if (arr.length < 2) {
        return arr
      }

      // 创建小桶
      const buckets = createBucket(arr, bucketSize)

      // 小桶排序 （调用插入排序的方法） 最后用concat 合并小桶
      return sortBuckets(buckets)
    }


    // 单独封装创建小桶的方法
    function createBucket (arr, bucketSize) {
      // 找到数组中的最大和最小值
      let minValue = Math.min(...arr)
      let maxValue = Math.max(...arr)
      // 计算桶的个数  最让人感到疑惑的地方
      const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1

      /* 
      分桶的策略： 希望前面的桶 比后面桶的元素要小  桶的个数：（最大值-最小值）/size + 1  最后的+1是为了最后一个值的索引
      */
      // 创建小桶
      const buckets = []
      for (let i = 0; i < bucketCount; i++) {
        buckets[i] = []
      }

      // 小桶里增加元素
      for (let i = 0; i < arr.length; i++) {
        // 创建索引
        const index = Math.floor((arr[i] - minValue) / bucketSize)
        // 添加元素
        buckets[index].push(arr[i])
      }
      return buckets
    }

    function sortBuckets (arr) {
      const sortArr = [] // 接收最后结果的数组

      for (let i = 0; i < arr.length; i++) {
        // 排除空桶的情况  如果是数据密度小 比较稀疏的情况下  测试：最大值改成100 那么会创建34个桶
        if (arr[i]) {
          insertSort(arr[i])
          sortArr.push(...arr[i]) // 合并数组         
        }
      }
      return sortArr
    }


    // 插入排序
    function insertSort (array) {
      const { length } = array;
      let temp;
      for (let i = 1; i < length; i++) {
        temp = array[i];
        let j = i;
        while (j > 0 && array[j - 1] > temp) {
          array[j] = array[j - 1];
          j--;
        }
        array[j] = temp;
      }
      return array
    }


    bucketSort([5, 4, 3, 2, 6, 1, 7, 10, 9, 8])
    console.log(bucketSort([5, 4, 3, 2, 6, 1, 7, 10, 9, 8]));
  </script>
</body>

</html>